Today, most electronic equipment contain and utilize switches. The ideal switch behaves like a mechanical switch. In the "on" state, a signal is passed through to a load without attenuation or non-linearity. In the "off" state, the switch acts as an open circuit. Electronic switches are usually comprised of transistor logic in order to take advantage of the quick rapid switching, typically within a quarter of a nanosecond. Field effect transistors (FETs) are normally employed in logic-switching applications. In practice, metal-oxide semiconductor FET (MOSFET) integrated circuits (rather than discrete transistors) are utilized in all digital logic and linear switch applications.
A specific application of switch technology is switch matrices, an example of which is shown in FIG. 1. Conceptually, a switch matrix 100 receives N inputs and produces M outputs. The function of switch matrix 100 is to allow M number of outputs to be selected from N number of inputs. Thus, various groupings of M number of outputs can be selected from the N inputs. Switch matrix 100 selects according to the control received as an input. When switch matrix 100 receives N input signals and produces M number of outputs, switch matrix 100 is referred to as an N.times.M matrix. The number of unique combinations of M outputs from switch matrix 100 for a given number of N inputs is given by the equation: EQU C=N!.div.((N-M)!.times.M!)
An example of a prior art implementation of a switch matrix is shown in FIG. 2. Referring to FIG. 2, inputs I1-I12 are coupled to outputs 01-04 using transistors. Inputs I1-I12 constitute rows in switch matrix 200. Outputs 01-04 constitute the columns of switch matrix 200. Since switch matrix 200 receives 12 inputs and produces 4 outputs, switch matrix 200 is referred to as a 12.times.4 matrix. The transistors of switch matrix 200 couple each of the I1-I12 inputs to each of the column outputs 01-04. The transistors of switch matrix 200 function as switches, such that the application of a control voltage on the gate of any one of the transistors allows the input to be coupled to the corresponding output. Thus, for a N.times.M switch matrix having twelve possible input connections taken as a grouping of four at any one time, the prior art switch matrix 200 would be a 12.times.4 matrix requiring forty-eight transistors (as shown).
The example of the switch matrix 200 in FIG. 2 is referred to as 100% connectable switch matrix. The concept of 100% connectable refers to a switch matrix wherein any possible M grouping of outputs can be taken without limitation. In this manner, all possible outputs can occur and are not restricted in any path by the inputs to the system. Thus, because any of the four outputs in switch matrix 200 can be taken for any of the twelve inputs, switch matrix 200 is 100% connectable.
As a switch matrix receives larger numbers of N inputs and larger numbers of M outputs, the switch matrix grows very large. A very large switch matrix typically can have hundreds of inputs and hundreds of outputs. Such a large switch matrix receiving many inputs and producing many outputs requires numerous transistors to switch the inputs to the proper output columns. Such a large switch matrix requires a large area to accommodate the number of transistors and is very costly in its implementation. Furthermore, the performance of such a matrix can be affected by the loading effect of the numerous transistors within the matrix. As more and more transistors are added, the capacitive load at any particular node in the switch becomes larger and larger and is driven by a fixed sized transistor. The size of the transistor can be increased, but then all the transistors must be increased and the load grows proportionally. This produces little gain, and, therefore, performance is very much a function of the number of devices in the switch matrix. Thus, the number of transistors corresponds to the area benefit and the performance benefit of the switch matrix. Hence, any reduction in the area or improvement in the performance can occur by reducing the number of switches (i.e., transistors) in the switch matrix.
Typically, in the prior art to reduce the number of switches (i.e., transistors) in the switch matrix, rows are eliminated. In this manner, the size of the switch matrix is reduced. By eliminating rows, inputs themselves are removed. Therefore, reducing the size by row reduction causes less than one hundred percent connectability and, thus, one hundred percent routability of inputs to outputs. Therefore, all possible outputs (i.e., M groupings) cannot be obtained. Less than one hundred percent connectability is permissible in some applications. However, in any less than one hundred percent connectability application, one must recheck the system to verify the proper outputs are obtained. Thus, an extra step is required to produce and generate the proper outputs from a set of inputs.
Another approach to eliminating and minimizing the size of a switch matrix is to intuitively remove transistors from the switch matrix. By performing this operation, the switch matrix can be reduced and still return the proper outputs (i.e., remain 100% connectable). However, performing such an operation on a system having large numbers of inputs and outputs is difficult because it is difficult to determine when the switch matrix is no longer capable of outputting one of its requisite outputs in response to one set of inputs. Thus, difficulty remains in using an intuitive approach when ascertaining whether one hundred percent connectability and routability (i.e., the routing of inputs to specific outputs) is still achieved.
As will be seen, the present invention provides a deterministic method to generate a minimal switch matrix. The matrix generated by the present invention is uniformally distributed with virtually no skew between inputs. Furthermore, the present invention generates a switch matrix of the minimum size required to result in one hundred percent routability and connectability. Also, the present invention provides the corresponding inter-connect layout for the circuit. Moreover, the present invention provides a method for routing the signals within the switch matrix in both a finite space and in a guaranteed time.